home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / prog_c / cuj0696.zip / DWYER.ZIP / GAP.TST / README.GAP < prev    next >
Text File  |  1995-12-27  |  5KB  |  152 lines
  1.  
  2. DESCRIPTION OF THE GAP TEST
  3.  
  4. Introduction
  5. ------------
  6.  
  7. As the name implies, the gap test considers intervals between
  8. a and b inclusive, where 0 <= a < b <= 1, in which random
  9. numbers fail to appear.  Pictorially, suppose a and b are
  10. situated like this:
  11.  
  12.     0    a    b    1
  13.     |-------|-------|-------|
  14.  
  15. The gap test scans for sequences in which all numbers fall
  16. _outside_ a and b.  The length of the sequence is the number
  17. of variates found.  A count is maintained of the number of
  18. times each such length occurs.  Thus, COUNT[0] contains the
  19. number of times that a gap of length 0 occurred, COUNT[1],
  20. the number of times that a gap length 1 occurred and so on.
  21.  
  22. The probability of an occurrence of a gap of length i, for
  23. 0 <= i <= t is:
  24.  
  25.     p[0] = p = (b-a)                                            | The [] denote
  26.     p[1] = p(1-p)   p[2] = p(1-p)^2  ... p[t-1] = p(1-p)^(t-1)  | subscripts,
  27.     p[t] = (1-p)^t                                              | The ^ denote
  28.                                 | exponents
  29. This is the only test that is controlled by the interval from
  30. 0 to 1.  All other tests are concerned with integers ranging
  31. from 0 to 32767 which is the range of values produced by the
  32. standard C library function, rand().
  33.  
  34. Running the Gap Test
  35. --------------------
  36.  
  37. To start program gaptst, you can say simply
  38.  
  39.     gaptst
  40.  
  41. and you will be prompted for the required inputs.
  42.  
  43. Alternatively, you can say
  44.  
  45.     gaptst < [myfile.inp]
  46.  
  47. and the program will take its input data from myfile.inp.
  48.  
  49. Seven input parameters are required:
  50.  
  51.     1.  Seed for the random number generator (-1 = Time of day)
  52.  
  53.            If you do not specify -1, the value entered must be less
  54.     than 65536.
  55.  
  56.     2.  Specification of generator to be tested
  57.  
  58.         If you are working interactively, you will see a list
  59.            of the generators that can be selected.  You enter the
  60.     character that represents your generator.  If you enter
  61.     a character that is not in the list, the library rand()
  62.     function will be used.
  63.  
  64.     3.  Lower boundary (a) of gap, 0 <= a < 1
  65.  
  66.     This sets the lower limit of the search.  This number
  67.     is converted to an integer between 0 and 32767.
  68.  
  69.     4.  Upper boundary (b) of gap, a < b <= 1
  70.  
  71.     This number must be greater than a.  It should also
  72.     be greater than a by at least .01.  If you specify
  73.     boundaries that are closer than that you are in for
  74.     a long wait because each iteration will require an
  75.     exorbitant number of variates.  For example, when
  76.     a = .01 and b = .011, about five million variates
  77.     are required per pass.  The total number of variates
  78.     needed would be in the neighborhood of 500,000,000.
  79.  
  80.     5.  Maximum gap length desired (number of variates)
  81.  
  82.     Gap lengths greater than this number are lumped into
  83.     one category.  All others are counted separately.
  84.  
  85.     6.  Minimum cell expectation (counts per category)
  86.  
  87.     This entry specifies the minimum number of counts
  88.     that you expect per gap length tallied.  If you
  89.     specify a number less than five, the number is set
  90.     to five (clamped).
  91.  
  92.     7.  Number of gaps to be tabulated (counted)
  93.  
  94.     The minimum number that program gaptst will use will
  95.     be specified in the prompt.  This number is a function
  96.     of gap limit (a, b), the maximum gap length and the
  97.     minimum cell expectation.
  98.  
  99. Execution of the Algorithm
  100. --------------------------
  101.  
  102. Once the input parameters have been processes and run-control
  103. variables have been set, the program will execute 100 chi-square
  104. runs as dictated by the input:
  105.  
  106.     1.    The generator of choice is called the number of times set by
  107.     input parameter 7 above. The cell (or category) corresponding
  108.     to the length of each gap is tallied.
  109.  
  110.     2.  A chi-square statistic is calculated for the array of tallies.
  111.  
  112.     3.    A probability for the chi-square statistic is calculated.
  113.  
  114.     4.    The probability is stored in an array.
  115.  
  116.     5.    A running account of the steps and the number of variates
  117.     generated lets you know that the program is executing.
  118.  
  119. When the 100 runs are complete, a Kolmogorov-Smirnov test is run on
  120. the array to obtain statistics Kn+ and Kn- and their corresponding
  121. probabilities.
  122.  
  123. Final printouts consist of the Kolmogorov-Smirnov statistics and
  124. probabilities and the number of random numbers generated during the
  125. test.
  126.  
  127. Figure.1g shows a sample input file should you elect to redirect the
  128. input.  Figure.2g shows what you can expect to see if you redirect the
  129. output during the run on the sample input shown in figure 1g.  Figure.3g
  130. shows what your screen should look like if you redirect stdout to a file.
  131.  
  132. Error Printouts
  133. ---------------
  134.  
  135.  *  Gap Boundaries Improperly Specified
  136.  
  137.     o You Have Specified Gap Limits 0 and 1. Please Reenter.
  138.  
  139.     o The Difference Between the Lower Boundary (0.01) and the
  140.       Upper Boundary (0.01001) is not Great Enough (0.00001)
  141.       You should specify limits that differ by .005 or more.
  142.  
  143. Timing Estimates
  144. ----------------
  145.  
  146. The run shown in figure 1.g required about 5.9 seconds on my
  147. Pentium 100.  Naturally, the time required depends on the
  148. generator (and the CPU).  For the data shown above, the range
  149. of times is from 5.9 seconds for the MSC library function rand()
  150. to 35.3 seconds for the generator by Stephen L. Moshier.  Both
  151. tests required about 4,096,000 random numbers.
  152.